package graph;

import org.junit.Test;

/*
 *@description 前缀树
 *@author hkfan
 *@version 1.0
 *@create 2025/5/19 15:34
 */
public class LeetCode_208 {

    class Trie{

        class Node{
            char value;
            int end;
            Node[] children;

            public Node() {
                this.children = new Node[26];
            }

            public Node(char value) {
                this.value = value;
                this.children = new Node[26];
            }
        }
        Node head;

        public Trie() {
            head = new Node();
        }

        public void insert(String word) {
            Node temp = head;
            for (int i = 0; i < word.length(); i++) {
                if (temp.children[word.charAt(i)-'a']==null){
                    Node node = new Node(word.charAt(i));
                    temp.children[word.charAt(i)-'a'] = node;
                }
                temp = temp.children[word.charAt(i)-'a'];
            }
            temp.end++;
        }

        public boolean search(String word) {
            Node temp = head;
            for (int i = 0; i < word.length(); i++) {
                if (temp.children[word.charAt(i)-'a']==null){
                    return false;
                }
                temp = temp.children[word.charAt(i)-'a'];
            }
            return temp.end>=1;
        }

        public boolean startsWith(String prefix) {
            Node temp = head;
            for (int i = 0; i < prefix.length(); i++) {
                if (temp.children[prefix.charAt(i)-'a']==null){
                    return false;
                }
                temp = temp.children[prefix.charAt(i)-'a'];
            }
            return true;
        }
    }

    @Test
    public void test(){
        Trie trie = new Trie();
        trie.insert("apple");
        System.out.println(trie.search("apple"));
        System.out.println(trie.search("app"));
    }



}
